package entity

// TraversalPreorder 深度优先
// root left right
func (n *PNode[T]) TraversalPreorder() []T {
	ts := make([]T, 0, 4)
	n.preorderTraversal(n, &ts)
	return ts
}

func (n *PNode[T]) TraversalInorder() []T {
	ts := make([]T, 0, 4)
	n.inorderTraversal(n, &ts)
	return ts
}
func (n *PNode[T]) TraversalPostorder() []T {
	ts := make([]T, 0, 4)
	n.postorderTraversal(n, &ts)
	return ts
}

func (n *PNode[T]) preorderTraversal(node *PNode[T], result *[]T) {
	if node.IsEmpty() {
		return
	}
	*result = append(*result, node.Data)
	n.preorderTraversal(node.Left, result)
	n.preorderTraversal(node.Right, result)
}
func (n *PNode[T]) inorderTraversal(node *PNode[T], result *[]T) {
	if node.IsEmpty() {
		return
	}
	n.preorderTraversal(node.Left, result)
	*result = append(*result, node.Data)
	n.preorderTraversal(node.Right, result)
}
func (n *PNode[T]) postorderTraversal(node *PNode[T], result *[]T) {
	if node.IsEmpty() {
		return
	}
	n.postorderTraversal(node.Left, result)
	n.postorderTraversal(node.Right, result)
	*result = append(*result, node.Data)
}

/*
TraversalLevel 判断二叉树是否为空，为空则直接返回。
令根节点入队
当队列不为空时，求出当前队列长度 Si
依次从队列中取出这Si  个元素，并对这些元素依次进行访问。然后将其左右孩子节点入队，然后继续遍历下一层节点。
当队列为空时，结束遍历。
*/
func (n *PNode[T]) TraversalLevel(node *PNode[T]) []T {
	if node.IsEmpty() {
		return nil
	}
	result := make([]T, 0, 4)
	queue := []*PNode[T]{node}
	for len(queue) > 0 {
		levelValue := make([]T, 0, 4)
		for _ = range len(queue) {
			curr := queue[0]
			levelValue = append(levelValue, curr.Data)
			// 第一层结束 添加第二层 至第二次循环
			if curr.Left != nil {
				queue = append(queue, curr.Left)
			}
			if curr.Right != nil {
				queue = append(queue, curr.Right)
			}
			queue = queue[1:]
		}
		if len(levelValue) > 0 {
			result = append(result, levelValue...)
		}
	}
	return result
}

//================

//是不能唯一地确定一棵二叉树的=>「前序遍历序列」和「后序遍历序列」 没有中确认左右子树

/*

从前序遍历顺序中得到当前根节点的位置在
通过在中序遍历中查找上一步根节点对应的位置 inorder[k] 从而将二叉树的左右子树分隔开，并得到左右子树节点的个数
从上一步得到的左右子树个数将前序遍历结果中的左右子树分开
构建当前节点，并递归建立左右子树，在左右子树对应位置继续递归遍历并执行上述三步，直到节点为空
*/

func (n *PNode[T]) BuildTreeFromPI(preorder, inorder []T) *PNode[T] {
	if len(preorder) != len(inorder) {
		return nil
	}
	return n.createTreeFromPI(preorder, inorder, len(inorder))
}

func (n *PNode[T]) createTreeFromPI(preorder, inorder []T, N int) *PNode[T] {
	if N == 0 {
		return nil
	}
	k := 0
	for preorder[0] != inorder[k] {
		k++
	}
	// 确认root 位置，按root所在区分左右子树 并得到左右子树节点的个数 k
	node := &PNode[T]{Data: preorder[0]}

	node.Left = n.createTreeFromPI(preorder[1:k+1], inorder[0:k], k)
	node.Right = n.createTreeFromPI(preorder[k+1:], inorder[k+1:], N-k-1)
	return node
}

//===

func (n *PNode[T]) BuildTreeFromIP(postorder, inorder []T) *PNode[T] {
	if len(postorder) != len(inorder) {
		return nil
	}
	return n.createTreeFromIP(inorder, postorder, len(inorder))
}

/*
根据后序遍历的顺序，可以找到根节点位置。然后在中序遍历的结果中可以找到对应的根节点位置，
就可以从根节点位置将二叉树分割成左子树、右子树。同时能得到左右子树的节点个数。
*/
func (n *PNode[T]) createTreeFromIP(inorder, postorder []T, N int) *PNode[T] {
	if N == 0 {
		return nil
	}
	k := 0
	for postorder[N-1] != inorder[k] {
		k++
	}
	const ex = `
		 1
	2		3
 4	   5      6
	 7   8
`
	//inorder   [2 4 5 7 8  1  3 6]
	//postorder [4 7 8 5 2  6 3  1]

	// 2 4 5 7 8
	// 4 7 8 5 2

	//2
	//4

	// 确认root 位置，按root所在区分左右子树 并得到左右子树节点的个数 k
	node := &PNode[T]{Data: inorder[k]}
	node.Left = n.createTreeFromIP(inorder[0:k], postorder[0:k], k)

	node.Right = n.createTreeFromIP(inorder[k+1:N], postorder[k:N-1], N-k-1)
	return node
}
